const { Node } = require("./Node");
// 二叉搜索树
class BSTree {
  constructor() {
    this.root = null;
  }
  _removeNode(node, data) {
    // 根节点都为空，不能删除任何值
    if (node === null) {
      return null;
    }
    // 删除的节点是根节点
    if (data === node.data) {
      // {1}:删除的是叶子节点，没有子节点
      // 当待删除的节点时叶子节点时, 直接将待删除的节点置空返回
      if (node.left === null && node.right === null) {
        return null;
      }
      // 当待删除的节点没有左子节点时，返回该节点的右孩子节点,并删除该节点
      if (node.left === null) {
        return node.right;
      }
      if (node.right === null) {
        return node.left;
      }
      /* 最后一种情况
        待删除的节点的左右子节点均存在,有两种做法：
        要么查找待删除节点左子树上的最大值，要么查找其右子树上的最小值
       */
      // 查找右节点的最小值
      let tempNode = this.getMinNode(node.right);
      node.data = tempNode.data; //右子树的最小值，替换要删除的值
      node.right = this._removeNode(node.right, tempNode.data);
      return node;
    }
    // 删除的节点在左节点
    else if (data < node.data) {
      node.left = this._removeNode(node.left, data);
      return node;
    } else {
      node.right = this._removeNode(node.right, data);
      return node;
    }
  }
  remove(data) {
    this._removeNode(this.root, data);
  }
  insert(data) {
    let newNode = new Node(data, null, null);
    if (!this.root) {
      // 不存在根节点时，将新节点设置为根节点
      this.root = newNode;
    } else {
      let currNode = this.root;
      let parentNode = null;
      while (true) {
        // 做为暂时保存变量
        parentNode = currNode;
        // 插入的值，小于父节点的值，插入到左侧
        if (newNode.data < currNode.data) {
          // 更新currNode为左侧的子节点
          currNode = currNode.left;
          // 一直查找直到没有左节点时，将新节点newNode设置为parentNode的左节点
          if (!currNode) {
            parentNode.left = newNode;
            break;
          }
        } else if (newNode.data > currNode.data) {
          currNode = currNode.right;
          if (!currNode) {
            parentNode.right = newNode;
            break;
          }
        } else if (newNode.data == currNode.data) {
          this.count++;
          break;
        }
      }
    }
  }
  // 在二叉树中进行搜索
  find(data) {
    let currNode = this.root;
    // 从根开始查找
    while (currNode) {
      if ((currNode.data = data)) {
        return currNode;
      } else if (currNode.data > data) {
        currNode = currNode.left;
      } else if (currNode.data < data) {
        currNode = currNode.right;
      }
    }
    return null;
  }
  getMinNode(node = this.root) {
    let curNode = node;
    while (curNode.left) {
      curNode = curNode.left;
    }
    return curNode;
  }
  getMaxNode(node = this.root) {
    let curNode = node;
    while (curNode.right) {
      curNode = curNode.right;
    }
    return curNode;
  }
  //----二叉树遍历---

  // 中序递归遍历
  inOrderRec(node = this.root) {
    // 先左，后根，再右
    let result = "";
    if (node !== null) {
      result += this.inOrderRec(node.left);
      result += `->${node.data}`;
      result += this.inOrderRec(node.right);
    }
    return result;
  }

  // 中序非递归遍历
  inOrderNonRec(node = this.root) {
    // 非递归遍历借助栈结构
    let stack = [];
    let result = "";
    while (node || stack.length) {
      if (node) {
        // 节点存在，先将节点入栈
        stack.push(node);
        // 使用节点的左子节点 更新节点，然后继续入栈
        node = node.left;
      } else {
        // 左子节点不存在了。执行出栈，后进先出
        node = stack.pop();
        result += `->${node.data} `;
        // 使用节点的右子节点 更新节点，然后入栈
        node = node.right;
      }
    }
    return result;
  }

  // 前序递归遍历, 1:访问根节点。2:前序遍历左子树。3:前序遍历右子树。
  preOrderRec(node = this.root) {
    // 先根，后左，再右
    let result = "";
    if (node !== null) {
      result += node === this.root ? `${node.data}` : `->${node.data}`;
      result += this.preOrderRec(node.left);
      result += this.preOrderRec(node.right);
    }
    return result;
  }

  // 前序遍历非递归方法
  preOrderNonRec(node = this.root) {
    //非递归的遍历时，算法需要借助一个栈
    let stack = [];
    let result = "";
    // 当节点存在或者栈不空时
    while (node || stack.length > 0) {
      if (node) {
        // 访问根节点
        result += `->${node.data} `;
        // 根节点入栈
        stack.push(node);
        // 根之后先遍历左子树
        node = node.left;
      } else {
        // 从栈中取出根节点
        node = stack.pop();
        // 遍历根节点的右子树
        node = node.right;
      }
    }
    return result;
  }

  // 后序遍历递归方法
  postOrderRec(node = this.root) {
    // 先左，后右，再根
    let result = "";
    if (node !== null) {
      result += this.postOrderRec(node.left);
      result += this.postOrderRec(node.right);
      result += `->${node.data}`;
    }
    return result;
  }

  // 后序遍历非递归的方法
  postOrderNonRec(node = this.root) {
    // 左右根
    let stack = [];
    let ret = node;
    let result = "";
    while (node || stack.length) {
      // 第一步现将根节点以及左节点依次入栈
      if (node) {
        // 根节点存在，将节点入栈
        stack.push(node);
        // 更新node节点，为左子节点，存在的话继续入栈，不存在就走else操作
        node = node.left;
      } else {
        // 获取栈顶节点，首次获取的值为7节点
        node = stack[stack.length - 1];
        // 如果node有右节点且未访问过
        if (node.right && node.right != ret) { // node.right != ret不同才进入右子节点入栈操作，如果已经处理过就不能进入
          node = node.right;
          // 将右节点入栈
          stack.push(node);
          node = node.left; // 再次查找此时右节点上是否有左节点
        } else {
          // 首先会进入这里开始遍历左子节点
          // 取出栈结构中的节点
          node = stack.pop();
          result += `->${node.data} `;
          // 记录下节点，防止进入无限循环
          ret = node;
          node = null;
        }
      }
    }
    return result;
  }

  // 层次遍历
  levelOrder(node = this.root) {
    //   进行层次遍历，需要借助队列
    // 首先将二叉树的根节点入队列，然后出队，访问该节点，如果它的左子树不空，则将左子树的根节点入队。如果它的右子树不为空，则将右子树的根节点入队。
    let queue = [];
    let result = "";
    // 根节点入队列
    queue.push(node);
    while (queue.length > 0) {
      // 获取队列的开头
      node = queue.shift();
      // 记录二叉树节点的值
      result += `->${node.data} `;
      if (node.left) {
        // 左子节点入队
        queue.push(node.left);
      }
      if (node.right) {
        // 右子节点入队
        queue.push(node.right);
      }
    }
    return result.substring(2);
  }

  // 知道二叉树的先序和中序排列，重建二叉树
  /**
   * @param {Array} preArr 先序序列
   * @param {Array} midArr 中序序列
   * @param {Number} pBeg 先序序列的第一个下标
   * @param {Number} pEnd 先序序列的最后一个下标
   * @param {Number} mBeg 中序序列的第一个下标
   * @param {Number} mEnd 中序序列的最后一个下标
   */
  preInCreate(preArr, midArr, pBeg, pEnd, mBeg, mEnd) {
    let lLen = 0,
      rLen = 0;
    let splitIdx = -1;
    // 建立根节点，先序的开头就是根
    let node = new Node(preArr[pBeg], null, null);
    if (!this.root) {
      this.root = node;
    }
    // 利用根节点即【20】 在中序序列中进行划分
    // 先序序列 20 ->13 ->7 ->9 ->15 ->14 ->42 ->22 ->21 ->24 ->57
    // 中序序列 7 ->9 ->13 ->14 ->15 ->20 ->21 ->22 ->24 ->42 ->57
    for (let i = mBeg; i <= mEnd; i++) {
      // 用先序的根【20】，在中序列查找，查出索引位置，即20所处的位置
      if (midArr[i] == preArr[pBeg]) {
        splitIdx = i;
        break;
      }
    }
    // 根据20所处的索引位置，求出左右子树的长度
    if (splitIdx > -1) {
      lLen = splitIdx - mBeg; // 左子树的长度 5， 【7 ->9 ->13 ->14 ->15】
      rLen = mEnd - splitIdx; // 右子树的长度 5， 【21 ->22 ->24 ->42 ->57】
    }

    // 递归建立左子树
    if (lLen) {
      node.left = this.preInCreate(
        preArr,
        midArr,
        pBeg + 1,
        pBeg + lLen,
        mBeg,
        mBeg + lLen - 1
      );
    } else {
      node.left = null;
    }

    // 递归建立右子树
    if (rLen) {
      node.right = this.preInCreate(
        preArr,
        midArr,
        pEnd - rLen + 1,
        pEnd,
        mEnd - rLen + 1,
        mEnd
      );
    } else {
      node.right = null;
    }

    return node;
  }
  // 获得二叉树中节点个数
  getNodeNumber(node = this.root) {
    let count = 0;
    if (node) {
      let queue = [];
      queue.push(node);
      while (queue.length) {
        node = queue.shift();
        count++;
        if (node.left) {
          queue.push(node.left);
        }
        if (node.right) {
          queue.push(node.right);
        }
      }
      return count;
    }
  }
  // 使用递归方式计算
  getNodeNumber2(node = this.root) {
    let count = 0;
    if (node) {
      count++;
      count += this.getNodeNumber2(node.left);
      count += this.getNodeNumber2(node.right);
    }
    return count;
  }

  // 获得二叉树中叶子节点的个数，没有left和right子节点是时才+1
  getLeafNodeNumber(node = this.root) {
    let count = 0;
    let queue = [];
    queue.push(node);
    while (queue.length) {
      node = queue.pop();
      if (node.left) {
        queue.push(node.left);
      }
      if (node.right) {
        queue.push(node.right);
      }
      if (!node.left && !node.right) {
        count++;
      }
    }
    return count;
  }
  getLeafNodeNumber2(node = this.root) {
    // 每次递归的结束条件
    if (!node) {
      return 0;
    }
    if (!node.left && !node.right) {
      return 1;
    }

    let leftNum = this.getLeafNodeNumber2(node.left);
    let rightNum = this.getLeafNodeNumber2(node.right);

    return leftNum + rightNum;
  }

  // 获取二叉树的深度
  getTreeDepth(node = this.root) {
    let depth = 0;
    if (node) {
      depth++;
      if (node.left && !node.right) {
        depth = this.getTreeDepth(node.left) + 1;
      }
      if (node.right && !node.left) {
        depth = this.getTreeDepth(node.right) + 1;
      }
      if (node.left && node.right) {
        depth =
          this.getTreeDepth(node.left) > this.getTreeDepth(node.right)
            ? this.getTreeDepth(node.left) + 1
            : this.getTreeDepth(node.right) + 1;
      }
    }
    return depth;
  }

  // 计算指定层数节点的个数
  //   使用一个变量来保存当前层数节点的个数，用这个变量作为内层循环结束的标识
  getLevelNodeNumber(level, node = this.root) {
    if (node) {
      // depth保存查找的层级
      let depth = 1;
      let queue = [];
      queue.push(node);
      if (depth === level) {
        return queue.length;
      }
      while (true) {
        //使用size保存当前层级节点的个数
        let size = queue.length;
        if (size === 0) {
          return;
        }
        // size有值，说明还是在当前层级
        while (size) {
          node = queue.shift();
          if (node.left) {
            queue.push(node.left);
          }
          if (node.right) {
            queue.push(node.right);
          }
          size--;
        }
        depth++;
        if (depth === level) return queue.length;
      }
    }
  }

  // 判断二叉树是不是完全二叉树
  // 补洞法：采用层序遍历，如果遇到一个空节点，则后边的节点都是空节点才是完全二叉树，否则就不是完全二叉树
  isCompleteTree1(node = this.root) {
    let queue = [];
    let flag = false;
    queue.push(node);
    while (queue.length) {
      node = queue.shift();
      // 如果节点存在
      if (node) {
        if (flag) {
          return false;
        }
        queue.push(node.left);
        queue.push(node.right);
      } else {
        // 节点不存在，说明出现了空节点，空节点就设置flag为true，如果后边没有任何节点，则为完全二叉树
        // 如果后边还有节点，再次进入到if(node)中，则是非完全二叉树
        flag = true;
      }
    }
    return true;
  }
  //《1》如果一个节点只有右子节点，则不是完全二叉树。
  //《2》当层序遍历到一个不是叶子节点的节点时【肯定是有左子节点或者右子节点】，如果其前面的节点没有右孩子节点，则不是完全二叉树。
  isCompleteTree2(node = this.root) {
    let queue = [];
    let noRight = false;
    queue.push(node);
    while (queue.length) {
      node = queue.shift();
      // 对应注释《1》
      if (!node.left && node.right) {
        return false;
      }
      //遇到一个非叶子节点 且其前面的节点没有右孩子节点
      if ((node.left || node.right) && noRight) {
        return false;
      }
      if (node.left) {
        queue.push(node.left);
      }
      if (node.right) {
        queue.push(node.right);
      } else {
        // 没右子节点，但是后续的节点还是有子节点的枪口
        noRight = true;
      }
    }
    return true;
  }

  // 求二叉树的镜像
  invertTree(node = this.root) {
    if (!node) {
      return;
    }
    // 建立一个临时存放节点的变量
    let tempNode = node.left;
    node.left = node.right;
    node.right = tempNode;

    this.invertTree(node.left);
    this.invertTree(node.right);
  }
}
let myTree = new BSTree();

myTree.insert(20);
myTree.insert(13);
myTree.insert(7);
myTree.insert(9);
myTree.insert(15);
myTree.insert(14);
myTree.insert(42);
myTree.insert(22);
myTree.insert(21);
myTree.insert(24);
myTree.insert(57);
// myTree.insert(6);
// myTree.insert(16);
// console.log(myTree.getMaxNode());
// console.log(myTree.getMinNode());
// myTree.remove(14);
// console.log(myTree.getMinNode());
// myTree.remove(42);
// console.log(myTree.getMaxNode());
// console.log(myTree.levelOrder());
// console.log(myTree.postOrderNonRec());
// let preOrder = [20, 13, 7, 9, 15, 14, 42, 22, 21, 24, 57];
// let inOrder = [7, 9, 13, 14, 15, 20, 21, 22, 24, 42, 57];
// let inLstIdx = inOrder.length - 1;
// let preLstIdx = preOrder.length - 1;

// let myTree = new BSTree();

// myTree.preInCreate(preOrder, inOrder, 0, preLstIdx, 0, inLstIdx);

// console.log(myTree.inOrderNonRec()); // 7 9 13 14 15 20 21 22 24 42 57
// console.log(myTree.preOrderNonRec()); //  20 13 7 9 15 14 42 22 21 24 57
console.log(myTree.postOrderNonRec());
// console.log(myTree.getLeafNodeNumber());
// console.log(myTree.getTreeDepth());

// console.log("计算level层级节点个数：", myTree.getLevelNodeNumber(4));
console.log("判断是否是完全二叉树：", myTree.isCompleteTree2());
// 翻转二叉树
// myTree.invertTree();
// console.log(myTree.inOrderNonRec());
